﻿#region

using System.Text;

#endregion

namespace AdvancedTraining.Lesson50;

/// <summary>
/// LeetCode 588. 设计内存文件系统
/// 设计一个内存文件系统，模拟以下功能：
/// 1. ls(path)：列出指定路径下的文件和目录
/// 2. mkdir(path)：创建目录
/// 3. addContentToFile(filePath, content)：向文件添加内容
/// 4. readContentFromFile(filePath)：读取文件内容
/// </summary>
/// <remarks>
/// 算法思路：
/// 1. 使用树形结构表示文件系统，每个节点可以是目录或文件
/// 2. 使用SortedDictionary保证文件和目录按字典序排列
/// 3. 使用StringBuilder存储文件内容，支持内容追加
/// 4. 通过路径分割和遍历找到目标节点
///
/// 时间复杂度：
/// - ls(path): O(m + nlogn)，其中m是路径深度，n是子节点数量
/// - mkdir(path): O(m)，其中m是路径深度
/// - addContentToFile(path, content): O(m + k)，其中m是路径深度，k是内容长度
/// - readContentFromFile(path): O(m)，其中m是路径深度
///
/// 空间复杂度：O(N)，其中N是文件系统中总节点数
/// </remarks>
public class DesignInMemoryFileSystem //leetcode_0588
{
    /// <summary>
    /// 内存文件系统实现类
    /// </summary>
    public class FileSystem
    {
        private readonly Node _head = new("");

        /// <summary>
        /// 列出指定路径下的文件和目录
        /// </summary>
        /// <param name="path">路径，如 "/a/b"</param>
        /// <returns>文件名或目录名列表，按字典序排列</returns>
        public List<string> Ls(string path)
        {
            var ans = new List<string>();
            var cur = _head;
            var parts = path.Split('/');
            var n = parts.Length;

            // 遍历路径，找到目标节点
            for (var i = 1; i < n; i++)
            {
                if (!cur.NextDict.ContainsKey(parts[i])) return ans;
                cur = cur.NextDict[parts[i]];
            }

            // cur指向了path的最后节点
            if (cur.Content == null) // 目录节点
                ans.AddRange(cur.NextDict.Keys);
            else // 文件节点
                ans.Add(cur.Name);

            return ans;
        }

        /// <summary>
        /// 创建目录
        /// </summary>
        /// <param name="path">要创建的目录路径</param>
        public void Mkdir(string path)
        {
            var cur = _head;
            var parts = path.Split("/");
            var n = parts.Length;
            for (var i = 1; i < n; i++)
            {
                if (!cur.NextDict.ContainsKey(parts[i]))
                    cur.NextDict[parts[i]] = new Node(parts[i]);
                cur = cur.NextDict[parts[i]];
            }
        }

        /// <summary>
        /// 向文件添加内容
        /// </summary>
        /// <param name="path">文件路径</param>
        /// <param name="content">要添加的内容</param>
        public void AddContentToFile(string path, string content)
        {
            var cur = _head;
            var parts = path.Split("/");
            var n = parts.Length;

            // 遍历到文件所在目录
            for (var i = 1; i < n - 1; i++)
            {
                if (!cur.NextDict.ContainsKey(parts[i]))
                    cur.NextDict[parts[i]] = new Node(parts[i]);
                cur = cur.NextDict[parts[i]];
            }

            // 来到的是倒数第二的节点了！注意for！
            if (!cur.NextDict.ContainsKey(parts[n - 1]))
                cur.NextDict[parts[n - 1]] = new Node(parts[n - 1], "");
            cur.NextDict[parts[n - 1]].Content?.Append(content);
        }

        /// <summary>
        /// 读取文件内容
        /// </summary>
        /// <param name="path">文件路径</param>
        /// <returns>文件内容</returns>
        public string ReadContentFromFile(string path)
        {
            var cur = _head;
            var parts = path.Split("/");
            var n = parts.Length;
            for (var i = 1; i < n; i++)
            {
                if (!cur.NextDict.ContainsKey(parts[i]))
                    cur.NextDict[parts[i]] = new Node(parts[i]);
                cur = cur.NextDict[parts[i]];
            }

            return cur.Content!.ToString();
        }

        /// <summary>
        /// 文件系统节点类
        /// </summary>
        private class Node
        {
            // content == null 意味着这个节点是目录
            // content != null 意味着这个节点是文件
            public readonly StringBuilder? Content;

            // 文件名、目录名
            public readonly string Name;
            public readonly SortedDictionary<string, Node> NextDict;

            // 构造目录
            public Node(string n)
            {
                Name = n;
                Content = null;
                NextDict = new SortedDictionary<string, Node>();
            }

            // 构造文件，c是文件内容
            public Node(string n, string c)
            {
                Name = n;
                Content = new StringBuilder(c);
                NextDict = new SortedDictionary<string, Node>();
            }
        }
    }

    /// <summary>
    /// 运行测试用例
    /// </summary>
    public static void Run()
    {
        Console.WriteLine("=== 内存文件系统测试 ===");

        var fileSystem = new FileSystem();

        // 测试用例1：创建目录并列出根目录
        Console.WriteLine("测试用例1: 创建目录并列出根目录");
        fileSystem.Mkdir("/a");
        var result1 = fileSystem.Ls("");
        Console.WriteLine($"创建/a后根目录内容: [{string.Join(", ", result1)}]");
        Console.WriteLine(result1.Count == 1 && result1[0] == "a" ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例2：添加文件并列出目录
        Console.WriteLine("测试用例2: 添加文件并列出目录");
        fileSystem.AddContentToFile("/a/b.txt", "Hello World");
        var result2 = fileSystem.Ls("/a");
        Console.WriteLine($"创建/a/b.txt后/a目录内容: [{string.Join(", ", result2)}]");
        Console.WriteLine(result2.Count == 1 && result2[0] == "b.txt" ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例3：读取文件内容
        Console.WriteLine("测试用例3: 读取文件内容");
        var content1 = fileSystem.ReadContentFromFile("/a/b.txt");
        Console.WriteLine($"读取/a/b.txt内容: '{content1}'");
        Console.WriteLine(content1 == "Hello World" ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例4：追加文件内容
        Console.WriteLine("测试用例4: 追加文件内容");
        fileSystem.AddContentToFile("/a/b.txt", " Again");
        var content2 = fileSystem.ReadContentFromFile("/a/b.txt");
        Console.WriteLine($"追加内容后读取/a/b.txt: '{content2}'");
        Console.WriteLine(content2 == "Hello World Again" ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例5：创建多层目录
        Console.WriteLine("测试用例5: 创建多层目录");
        fileSystem.Mkdir("/a/c");
        fileSystem.Mkdir("/a/c/d");
        fileSystem.AddContentToFile("/a/c/d/e.txt", "Nested File");
        var result3 = fileSystem.Ls("/a/c/d");
        Console.WriteLine($"创建嵌套目录后/c/d目录内容: [{string.Join(", ", result3)}]");
        Console.WriteLine(result3.Count == 1 && result3[0] == "e.txt" ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例6：列出文件而不是目录
        Console.WriteLine("测试用例6: 列出文件而不是目录");
        var result4 = fileSystem.Ls("/a/c/d/e.txt");
        Console.WriteLine($"列出文件/e.txt: [{string.Join(", ", result4)}]");
        Console.WriteLine(result4.Count == 1 && result4[0] == "e.txt" ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例7：测试不存在路径
        Console.WriteLine("测试用例7: 测试不存在路径");
        var result5 = fileSystem.Ls("/nonexistent");
        Console.WriteLine($"访问不存在路径: [{string.Join(", ", result5)}]");
        Console.WriteLine(result5.Count == 0 ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        // 测试用例8：复杂文件结构
        Console.WriteLine("测试用例8: 复杂文件结构");
        fileSystem.Mkdir("/projects");
        fileSystem.AddContentToFile("/projects/readme.md", "# Project README");
        fileSystem.AddContentToFile("/projects/main.cs", "Console.WriteLine(\"Hello\");");
        fileSystem.Mkdir("/projects/src");
        fileSystem.AddContentToFile("/projects/src/utils.cs", "public static class Utils {}");

        var rootResult = fileSystem.Ls("");
        var projectsResult = fileSystem.Ls("/projects");
        var srcResult = fileSystem.Ls("/projects/src");

        Console.WriteLine($"根目录: [{string.Join(", ", rootResult)}]");
        Console.WriteLine($"projects目录: [{string.Join(", ", projectsResult)}]");
        Console.WriteLine($"src目录: [{string.Join(", ", srcResult)}]");

        bool test8Passed = rootResult.Count == 2 &&
                         projectsResult.Count == 3 &&
                         srcResult.Count == 1;
        Console.WriteLine(test8Passed ? "✓ 通过" : "✗ 失败");
        Console.WriteLine();

        Console.WriteLine("=== 算法说明 ===");
        Console.WriteLine("文件系统结构：使用树形结构，每个节点可以是目录或文件");
        Console.WriteLine("目录节点：Content为null，NextDict存储子节点");
        Console.WriteLine("文件节点：Content为StringBuilder，NextDict为空");
        Console.WriteLine("路径操作：通过Split分割路径，遍历找到目标节点");
        Console.WriteLine("排序保证：使用SortedDictionary确保文件按字典序排列");
        Console.WriteLine("时间复杂度：ls-O(m+nlogn), mkdir-O(m), addContent-O(m+k), readContent-O(m)");
    }
}